// 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

// 示例 1：

// 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
// 输出：[[1,6],[8,10],[15,18]]
// 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
// 示例 2：

// 输入：intervals = [[1,4],[4,5]]
// 输出：[[1,5]]
// 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
var merge = function (intervals) {
  intervals = intervals.sort((a, b) => a[0] - b[0]);
  let k = 0;
  while (k < intervals.length) {
    let i = k + 1;
    let [start, end] = intervals[k];
    while (i < intervals.length) {
      const [_start, _end] = intervals[i];
      if (_start > end || _end < start) {
        i++;
        continue;
      }
      intervals.splice(i, 1);
      start = Math.min(start, _start);
      intervals[k][0] = start;
      end = Math.max(end, _end);
      intervals[k][1] = end;
    }
    k++;
  }
  return intervals;
};
// 网上优解
var merge2 = function (intervals) {
  if (intervals.length === 1) return intervals;

  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0]];

  for (let i = 1; i < intervals.length; ++i) {
    const last = merged[merged.length - 1];
    const current = intervals[i];

    if (last[1] >= current[0]) last[1] = Math.max(last[1], current[1]);
    else merged.push(current);
  }
  return merged;
};
const ans = merge([
  [
    [1, 10],
    [2, 3],
    [4, 5],
    [6, 7],
    [8, 9],
  ],
]);
console.log("ans: ", ans);
